package sorts;

import java.util.Arrays;

public class Programma16_16 {
    public int[] subSort(int[] array) {
        if (array.length < 2 || array == null) {
            int[] a = {-1, -1};
            return a;
        }
        int[] arr = new int[array.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = array[i];
        }
//        int[] arr = array;
        quickSort(array, 0, array.length - 1);

        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(array));


        int start = -1;
        int end = -1;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != array[i]) {
                start = i;
                break;
            }
        }

        for (int i = arr.length - 1; i > start; i--) {
            if (arr[i] != array[i]) {
                end = i;
                break;
            }
        }
        int[] res = {start, end};
        return res;
    }

    private void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int l = left, r = right;
        int key = arr[l];

        while (l < r) {
            while (l < r && key < arr[r]) r--;
            while (l < r && key >= arr[l]) l++;
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        arr[left] = arr[l];
        arr[l] = key;

        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 9, 7, 5};
        Programma16_16 p = new Programma16_16();
        p.subSort(arr);
    }


}
